package topkfrequent

import "container/heap"

// 获得前k个高频元素
//方法一：小顶堆
func topKFrequent(nums []int, k int) []int {
    map_num:=map[int]int{}
    //记录每个元素出现的次数
    for _,item:=range nums{
        map_num[item]++
    }
    h:=&IHeap{}
    heap.Init(h)
    //所有元素入堆，堆的长度为k
    for key,value:=range map_num{
        heap.Push(h,[2]int{key,value})
        if h.Len()>k{
            heap.Pop(h)
        }
    }
    res:=make([]int,k)
    //按顺序返回堆中的元素
    for i:=0;i<k;i++{
        res[k-i-1]=heap.Pop(h).([2]int)[0]
    }
    return res
}

//构建小顶堆
type IHeap [][2]int

func (h IHeap) Len()int {
    return len(h)
}

func (h IHeap) Less (i,j int) bool {
    return h[i][1]<h[j][1]   // 升序规则  sort接口用到
}

func (h IHeap) Swap(i,j int) {
    h[i],h[j]=h[j],h[i]
}

func (h *IHeap) Push(x interface{}){
    *h=append(*h,x.([2]int))
}
func (h *IHeap) Pop() interface{}{
    old:=*h
    n:=len(old)
    x:=old[n-1]
    *h=old[0:n-1]
    return x
}

// // 插入数据
// func (this *priporityQueue) Push(x int) {
// 	// 插入数据  每次插入之后需要调整结构
// 	this.q = append(this.q, x)
// 	// 调整
// 	this.adjustBottomUp()
// 	// 调整完毕，保证根为最大值
// }

// // 返回最大值，并弹出
// func (this *priporityQueue) Front() int{
// 	var res int = this.q[0]
// 	// 弹出并调整，与叶子节点交换
// 	n := len(this.q)
// 	// 判空
// 	if len(this.q) == 0 {
// 		return -1
// 	}
// 	this.q[0],this.q[n-1] = this.q[n-1],this.q[0]
// 	// 删除叶子节点
// 	this.q = this.q[:n-1]
// 	// 调整
// 	this.adjustBottomUp()
// 	return res
// }

// // 自底向上调整
// func (this *priporityQueue) adjustBottomUp() {
// 	// 调整，保证最大值到根部
// 	for i:=len(this.q)-1;i>=0; {
// 		// i元素的父节点，下标是  i/2
// 		// 如果i是奇数 则父节点是i/2
// 		var parent int
// 		if i%2==1 {
// 			parent = i/2
// 		}else {
// 			// 如果i是偶数 父节点是(i-1)/2
// 			parent = (i-1)/2
// 		}
// 		// 比较父子大小
// 		if this.q[parent] < this.q[i] {  // 子节点上升
// 			this.q[i],this.q[parent] = this.q[parent],this.q[i]
// 		}
// 		// 然后 当前节点变为parent下标
// 		i = parent
// 	}
// }